/**
 * @作者 zxy
 * @时间 2023-04-26 12:01
 * @说明 85. 最大矩形
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 */
public class Solution {
    public static void main(String[] args) {
        new Solution().maximalRectangle(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}});
    }

    /**
     * 执行用时：10 ms, 在所有 Java 提交中击败了68.98%的用户
     * 内存消耗：45.6 MB, 在所有 Java 提交中击败了41.32%的用户
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        int[][] rec = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int i1 = 0; i1 < matrix[i].length; i1++) {
                if (matrix[i][i1] == '1') {
                    if (i > 0) rec[i][i1] = rec[i - 1][i1] + 1;
                    else rec[i][i1] = 1;
                }
            }
        }
        int res = 0;
        for (int[] ints : rec) {
            for (int i1 = 0; i1 < ints.length; i1++) {
                int minHight = Integer.MAX_VALUE;
                for (int j = i1; j < ints.length; j++) {
                    minHight = Math.min(minHight, ints[j]);
                    res = Math.max(res, minHight * (j - i1 + 1));
                    if (minHight == 0) break;
                }
            }
        }
        return res;
    }
}
